package dataStructureAlgorithms;

import java.util.Arrays;

/**
 * @description: TODO
 * @author: wzj
 * @create: 2019/4/22 8:20
 */
public class Sort {
    public static void main(String[] args) {
        int[] arr=new int[]{4,6,2,7,3,5,1};
//        bubbleSort(arr);
//        selectSort(arr);
//        quickSort(arr,0,6,0);
//        insertSort(arr);
//        shellSort(arr);
//        mergeSort(arr,0,6);
//        heapSort(arr);
        radixSort(new int[]{1,21,72,333,22,65,4});
    }

    //TODO 基数排序
    public static void radixSort(int[] arr){
        //查找最大值
        int max=arr[0];
        for(int i=1;i<arr.length;i++){
            if(arr[i]>max){
                max=arr[i];
            }
        }
        int sortCount=(max+"").length();// 根据最大值的长度 判断是几位数 判断排序几次
        int[][] storeNum=new int[10][arr.length];//余数(0-9)对应的数组，用于存储arr对应的数值
        int[] storeNumIndex=new int[10];//存储storeNum[0][storeNumIndex[0]]到storeNum[9][storeNumIndex[9]]各自用到的下标
        for(int i=0,k=1;i<sortCount;i++,k*=10){//k用于求余数
            //存
            for(int j=0;j<arr.length;j++){
                int ys=arr[j]/k%10;//余数
                storeNum[ys][storeNumIndex[ys]]=arr[j];
                storeNumIndex[ys]++;
            }
            //取
            int index=0;
            for(int m=0;m<storeNum.length;m++){
                for(int n=0;n<storeNumIndex[m];n++){
                    arr[index]=storeNum[m][n];
                    storeNum[m][n]=0;//清除对应位置的值
                    index++;
                }
                storeNumIndex[m]=0;//清空对应的下标
            }
            System.out.println(Arrays.toString(arr));
        }
    }

    //TODO 堆排序
    /**
     * 大顶堆 升序
     * @param arr
     */
    public static void heapSort(int[] arr){
        //将数组调整为大顶堆，应该从最后一个非叶子节点开始调整，节点n的左子节点为2n+1，右为2n+2，
        // 完全二叉树一定有左子节点，所以最后一个非叶子节点用(arr.length-1)/2计算求出
        for(int i=(arr.length-1)/2;i>=0;i--){
            maxHeap(arr,i,arr.length);
        }
        //将大顶堆的第0和最后一个交换
        for(int i=arr.length-1;i>0;i--){
            int t=arr[i];
            arr[i]=arr[0];
            arr[0]=t;
            //交换之后，将剩下的再次构建成大顶堆
            maxHeap(arr,0,i);
        }
        System.out.println(Arrays.toString(arr));
    }
    /**
     * 将一个节点下的树调整为大顶堆
     * @param arr
     * @param index 非叶子节点下标
     * @param size 数组长度
     */
    public static void maxHeap(int[] arr,int index,int size){
        int lNode=2*index+1,rNode=2*index+2;//左右子节点下标
        if(lNode<size && arr[index]<arr[lNode]){
            int t=arr[lNode];
            arr[lNode]=arr[index];
            arr[index]=t;
            maxHeap(arr,lNode,size);
        }
        if(rNode<size && arr[index]<arr[rNode]){
            int t=arr[rNode];
            arr[rNode]=arr[index];
            arr[index]=t;
            maxHeap(arr,rNode,size);
        }
        /*int max=index;//记录大的节点的下标
        if(lNode<size && arr[max]<arr[lNode]){
            max=lNode;
        }
        if(rNode<size && arr[max]<arr[rNode]){
            max=rNode;
        }
        if(max!=index){//当节点值小于左或右子节点时，交换值
            int t=arr[index];
            arr[index]=arr[max];
            arr[max]=t;
            // 交换后，防止之前排好的堆乱了，所以要重新调整之前排好的堆
            maxHeap(arr,max,size);
        }*/
    }

    //TODO 归并排序
    /**
     * 归并
     * @param arr
     * @param low
     * @param high
     */
    public static void mergeSort(int[] arr,int low,int high){
        int middle=(high+low)/2;
        if(low<high){
            mergeSort(arr,low,middle);
            mergeSort(arr,middle+1,high);
            merge(arr,low,middle,high);
        }
    }
    public static void merge(int[] arr,int low,int middle,int high){
        System.out.println("low "+low+" middle "+middle+" high "+high);
        int[] t=new int[high-low+1];
        int i=low,j=middle+1,index=0;//循环中全部是<=，j必须是middle+1才可以。。。需要看
        while(i<=middle && j<=high){
            if(arr[i]<arr[j]){
                t[index]=arr[i];
                i++;
            } else {
                t[index]=arr[j];
                j++;
            }
            index++;
        }

        while(i<=middle){
            t[index]=arr[i];
            i++;
            index++;
        }

        while(j<=high){
            t[index]=arr[j];
            j++;
            index++;
        }

        for(int k=0;k<t.length;k++){
            arr[low+k]=t[k];
        }

        System.out.println(Arrays.toString(arr));
    }

    // TODO 插入排序
    /**
     * 【直接插入】
     * @param arr
     */
    public static void insertSort(int[] arr){
        int t,index;//要插入的数 要插入的数的下标
        for(int i=1;i<arr.length;i++){
            index=i;
            t=arr[i];
            //这个是一直比较，并比要插入的数大的数向后挪【推荐】
            while(i>0 && t<arr[i-1]){
                arr[i]=arr[i-1];
                i--;
            }
            arr[i]=t;//不满足while循环时，则插入
            i=index;
            System.out.println(Arrays.toString(arr));
/*

            index=i;
            //这个是插入时有小的则替换
            while(i>0 && arr[i]<arr[i-1]){
                t=arr[i];
                arr[i]=arr[i-1];
                arr[i-1]=t;
                i--;
            }
            i=index;
*/
        }
    }
    /**
     * 【希尔(缩小增量)排序】
     * @param arr
     */
    public static void shellSort(int[] arr){
        int t,index;
        for(int d=arr.length/2;d>0;d/=2){//几次增量
            for(int i=d;i<arr.length;i++){//根据增量插入排序
                /*t=arr[i];
                index=i;
                while(i-d>=0 && t<arr[i-d]){
                    arr[i]=arr[i-d];
                    i-=d;
                }
                arr[i]=t;
                i=index;*/

                for(int j=i-d;j>=0;j-=d){
                    if(arr[j]>arr[j+d]){
                        int temp = arr[j];
                        arr[j]=arr[j+d];
                        arr[j+d]=temp;
                    }
                }
                System.out.println(d+" "+Arrays.toString(arr));
            }
            System.out.println("************************");
        }
    }

    // TODO 交换排序
    /**
     * 【冒泡】
     * @param arr
     */
    public static void bubbleSort(int[] arr){
        int length=arr.length,temp;
        for(int i=0;i<length-1;i++){
            for(int j=0;j<length-1-i;j++){
                if (arr[j] >= arr[j+1]) {
                    temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
                System.out.println(Arrays.toString(arr));
            }
            System.out.println("**************");
        }
    }
    /**
     * 【快速】
     * @param arr
     */
    public static void quickSort(int[] arr,int start,int end,int i){
        int low=start,high=end;
        if (low < high) {
            int startVal=arr[low];
            while(low<high){
                while(low<high&&arr[high]>=startVal){//arr[high]>=startVal和arr[low]<=startVal必须是有一个地方有=，没有=，会死循环
                    high--;
                    System.out.println(high+"次数high："+(++i));
                }
                arr[low]=arr[high];
                System.out.println("次数high："+Arrays.toString(arr));
                while(low<high&&arr[low]<=startVal){
                    low++;
                    System.out.println(low+"次数low："+(++i));
                }
                arr[high]=arr[low];
                System.out.println("次数low："+Arrays.toString(arr));
            }
            arr[low]=startVal;
            quickSort(arr,start,low-1,i);
            quickSort(arr,low+1,end,i);
        }
    }

    // TODO 选择排序
    /**
     * 【简单选择】 不记录最小值的下标，直接交换
     * @param arr
     */
    public static void selectSort1(int[] arr){
        int t;
        for(int i=0;i<arr.length-1;i++){
            for(int j=i+1;j<arr.length;j++){
                if(arr[i]>=arr[j]){
                    t=arr[i];
                    arr[i]=arr[j];
                    arr[j]=t;
                }
                System.out.println(Arrays.toString(arr));
            }
            System.out.println("*********************");
        }
    }
    /**
     * 【简单选择】【推荐】 记录最小值的下标，最后交换
     * @param arr
     */
    public static void selectSort(int[] arr){
        int t,minIndex;
        for(int i=0;i<arr.length-1;i++){
            minIndex=i;
            for(int j=i+1;j<arr.length;j++){
                if(arr[j]<=arr[minIndex]){
                    minIndex=j;
                }
                System.out.println(minIndex+" "+Arrays.toString(arr));
            }
            t=arr[i];
            arr[i]=arr[minIndex];
            arr[minIndex]=t;
            System.out.println(Arrays.toString(arr));
            System.out.println("*********************");
        }
    }
}
